/*
Copyright (C) 2011 by the PSVN Research Group, University of Alberta
*/

#include <sys/time.h>
#include <vector>

using namespace std;

int64_t bfs_nodes = 0;
int64_t dfs_nodes = 0;
int64_t total_bfs_nodes = 0;
int64_t total_dfs_nodes = 0;

// search to depth d, checks for goal only at depth d
bool dfs(const state_t* state, const int d)
{
    dfs_nodes++;
    if (d == 0)
        return is_goal(state);
    int rule_used;
    func_ptr iter;
    state_t child;
    init_fwd_iter(iter);
    while((rule_used = next_fwd_iter(iter, state)) >= 0) {
        apply_fwd_rule(rule_used, state, &child);
        if (dfs(&child, d - 1))
            return true;
    }
    return false;
}

// iteratively performs dfs to max_depth 
// returns depth of goal or -1 if no goal by max_depth
int idfs(const state_t* state, const int max_depth)
{
    for (int d = 0; d <= max_depth; ++d)
        if (dfs(state, d))
            return d;
    return -1;
}

bool brfslk(const state_t* start_state, const int k)
{
    int rule_used;
    func_ptr iter;
    state_t state, child;
    vector<state_t> queue, next_queue;
    state_map_t *map = new_state_map();
    state_map_add(map, start_state, 0);
    queue.push_back(*start_state);
    bfs_nodes = 0;
    dfs_nodes = 0;

    int d = 0;
    bool found_goal = false;
    while (!found_goal) {
        while(queue.size() && !found_goal) {
            state = queue.back();
            queue.pop_back();
            bfs_nodes++;
            // if at root: perform iterated dfs to find shallowest goal
            if (d == 0) {
                int dd = idfs(&state, k);
                if (dd >= 0) {
                    found_goal = true;
                    d = dd;
                    break;
                }
            // if not at root: do dfs to depth k
            } else if (dfs(&state, k)) {
                found_goal = true; 
                d = d + k;
                break;
            }
            init_fwd_iter(iter);
            while((rule_used = next_fwd_iter(iter, &state)) >= 0) {
                apply_fwd_rule(rule_used, &state, &child);
                if(state_map_get(map, &child) == NULL) {
                    state_map_add(map, &child, d);
                    next_queue.push_back(child);
                }
            }
        }
        queue = next_queue;
        next_queue.clear();
        if (found_goal || queue.size() == 0)
            break;
        ++d;
    } 
    printf("d %d bfs %lu dfs %lu mem %lu\n", d, bfs_nodes, dfs_nodes, 
           map->max_entry * sizeof(state_map_entry_t));
    destroy_state_map(map);    
    total_bfs_nodes += bfs_nodes;
    total_dfs_nodes += dfs_nodes;
    return found_goal;
}

int main(int argc, char** argv)
{
    if(argc < 2) {
        fprintf(stderr, "usage: brfslk k\n");
        exit(-1);
    }
    int k;
    sscanf(argv[1], "%d", &k);

    struct timeval start, end;
    gettimeofday(&start, NULL);
    char line[4096];
    state_t state;
    for(size_t trials = 0;
        fgets(line, 4096, stdin) != NULL
            && read_state(line, &state) > 0;
        ++trials) 
    {
        printf("problem %lu: ", trials + 1);
        print_state(stdout, &state);
        printf("\n");
        brfslk(&state, k);
    }
    gettimeofday(&end, NULL);
    end.tv_sec -= start.tv_sec;
    end.tv_usec -= start.tv_usec;
    if(end.tv_usec < 0) {
        end.tv_usec += 1000000;
        --end.tv_sec;
    }
    printf("total: bfs %lu dfs %lu %zd.%06zd seconds\n",
           total_bfs_nodes, total_dfs_nodes, end.tv_sec, end.tv_usec);
    return 0;
}
